Advent of Code/2021

Trying out AoC with Javascript this year. I'd also planned to do it in Forth, but that seems like it's a bit too much work.
- Solutions at https://github.com/kunalb/AoC2021
Daily notes / reviews
- Day 1
  - 2356 / 4013
  - Wasted a lot of time because Blitzen's submit isn't working correctly any more, and I haven't bothered to fix it yet.
- Day 2
  - 5301 / 3850
  - Double checked that submit was broken and wasted an extra minute.
- Day 3
  - 3027 / 2774
- Day 4
  - 563 / 430
  - My best performance yet; getting somewhat comfortable with using Javascript. Mostly straightforward question; just needed to make sure I follow the instructions and don't make too many mistakes.
  - Finally figured out how to use the Deno LSP with emacs
- Day 5
  - 459 / 293
  - Brute forced it quickly by storing a map representing the grid and incrementing values
  - Trying to learn new pieces of javascript by cleaning up my solution.
- Day 6
  - 2046 / 871
  - Over thought this problem and did it with Dynamic programming instead of maintaining counters of fish.
- Day 7
  - 6987 / 4539
  - Greatly overthought my solution, but still submitted it within ~15 minutes or so.
  - But now AoC seems to be having issues.
- Day 8
  - 300 / 1090
  - Reading to the end first helped me do part 1 quickly
  - Expressing constraints was a little tricky, but worked out
  - Javascript's sets seem unnecessarily handicapped
- Day 9
  - 3435 / 1511
  - Messed up a lot while writing javascript and inserting answers
  - As well as < vs <=
  - I really miss using Python :)
  - Wrote my own javascript generator for the first time
- Day 10
  - 742 / 1285
  - Mostly wasted time using javascript incorrectly
- Day 11
  - 1592 / 1635
  - Lost a lot of time because I used a `for…in` loop on an array, which gives string indexes
  - Otherwise today was a modified game-of-life-like variant
- Day 12
  - 2038 / 1550
  - Wasted a little bit of time cloning objects incorrectly, and used a Set in the end
  - Trying out profiling to see if I can make it faster
- Day 13
  - 368 / 469
  - Not bad, good performance across both parts
  - struggled a little bit to print out values without a newline, and gave up
  - wasted some more time on Math.max.apply(<context>, actual array)
- Day 14
  - 183 / 258
  - Slowly inching towards the leaderboard, I hope I don't jinx myself
  - No clever javascript today, but I was missing python a lot while counting keys, etc.
- Day 15
  - 1327 / 2927
  - Forgot how to do Djikstra's algorithm, and initially solved part 1 with simple dynamic programming
  - …and it worked for Part 1, but didn't for Part 2
  - particularly because this can't handle loops/going backwards in a DP based solution
  - implemented djikstra's without a heap (because javascript doesn't have one)
  - which lead to a 3 minute solution for part 2
  - Looking through reddit, 2 solutions I hadn't considered
    - Dial's algorithm, which uses buckets instead of a priority queue
    - Repeatedly re-doing a dynamic programming-like approach till it converges
      - which I'm not sure I understand
      - but I'm beginning to suspect reduces to djikstra's algorithm with constant relaxation
      - Wikipedia pointed me to this paper on the connection between dynamic programming & djikstra's algorithm
      - Apparently this is Successive Approximation
        
        Solve by pulling for improvements
        
        or pushing improvements
- Day 16
  - 1488 / 2064
  - Pretty slow today, but I enjoyed myself a lot
    - It was tempting to do string manipulation (.toString(2), and parseInt(…)) to avoid thinking about bits, but I persevered
  - Learnt about how to use Uint8Array, BigInt for the first time
- Day 17
  - 1900 / 1304
  - Slow again, because I was trying hard to find a non brute force solution
    - but the requirement for integer solutions finally persuaded me not to bother
- Day 18
  - 378 / 326
  - Not bad, this was something of a slog of tree manipulation
  - I could probably do this with less code and more implicit tree manipulation
    - but explicitly having a tree structure kept bugs down
    - and let me do a quick in-order traversal
  - Ran across betaveros's blog on AoC today, which is excellent
- Day 19
  - 2254 / 2108
  - Got badly stuck, because I didn't realize that axis could be completely misaligned such that x, y, z => x, z, y
    - Even though this was one of the examples
  - Also took a lot of effort to work with javascript's primitives, though I have a reasonably clean solution by the end
  - Also wasted a lot of time with broken reduces/sorting, etc.
  - Slightly embarrassed to see how small and compact others' solutions are
- Day 20
  - 542 / 404
  - Really simple day: just 2 catches
    - it's possible for all bulbs to light up if the enhancement image is 0
    - building the next image while adjusting the coordinates for the primary image
  - I feel somewhat robbed by javascript because of strange array behavior that wasted 15 of the 30 minutes on the problem
    - which was a really sad mistake on my part while trying to initialize a 2 dimensional array
    - I did
      let nextImage = new Array(4).fill(new Array(4).fill("."));
    - which creates a 2-dimensional array, filled with the same array 4 times
- Day 21
  - 1372 / 2301
  - A little sleepy and disappointingly slow
  - It took me some time to grok the rules of the game for part 1 and implement them correctly
  - … and then to realize that memoization would lead to victory for part 2
    - given the values would end up repeating after a few turns
  - Still a nice problem today with a fairly distinct part 1 & 2
  - Notes from others' solutions
    - One player treated the memoized values as "all games in progress" and kept increasing those
    - Another very elegantly swapped player1/player2 values as arguments to the recursive function to show who's going first
- Day 22
  - 1010 / 10372
  - Looks like a range-tree/oct-tree, but I haven't implemented one in a long time.
  - Didn't actually need it – my solution was good enough, just doing unnecessary work that was trivial to fix after a good night's sleep.
    - Intersected cuboids carefully to get ranges to solve.
  - https://github.com/leyanlo/advent-of-code/blob/main/2021/day-22.js is an elegant solution that uses negative cuboids, and is significantly smaller than mine.
- Day 23
  - 334 / 5243
  - Manually solved the first one.
  - Tried to manually solve the second one while writing pathfinding code to aid me at the same time.
  - Working solution that takes 2 minutes
  - Pretty much brute force with pruning paths and semi-clever caching.
  - Looking at reddit suggests a fast solution would be to treat each state as a node in a graph and do djikstra's algorithm on it by cost.
- Day 24
  - 1169 / 1113
  - I'm kind of impressed at how fast everyone reverse engineered everything
  - Pretty proud of my constraint based solution which is pretty much O(instructions)
    - The program is a series of 14 steps on z, which reduces to:
      function step(p1, p2, p3) { w = inputs.next().value; x = z % 26 + p2; z = Math.floor(z / p1); if (x != w) { z = z * 26 + w + p3; } // console.log({step: ++i, w, x, y, z}); }
    - Expanding this a little bit leads to constraints on the inputs: 1 <= input <= 9,
    - But we also want to make sure z reaches 0:
      - z can only reduce when p1 != 1
      - which explicitly sets up relationships on 7 values
      - the constants/parameters end up giving a range on the "free" values
      - setting the "free" values to their maximum & minimum possible values respectively solves the problem.
  - And fairly curious about how Reddit did it:
    - Brute force with a reduced search space
    - Python to directly evaluate it by heavily relying on caching
    - A few others who derived the constraints like I did
    - Using Z3 SMT Solver: https://gist.github.com/AdibSurani/c047a0f0d3d9bc294337cb58da16173e
- Day 25
  - 1283 / 1009
  - A nice and gentle puzzle, though with several edge cases – all of which I felt like I managed to hit :)
  - It's a relief to wrap up this year's AoC – I learned a lot, and mostly enjoyed myself; but there's also a tinge of disappointment for not making it to the leaderboard.
    - I do feel significantly more comfortable with Javascript
    - And find it a little bit unhappy about the ergonomics.
    - Deno makes it really convenient to run though.
Notes on Javascript
- All my favorite old pieces from javascript work for the most part.
- Deno seems really cool and has been a pleasure to work with.
- Configuring emacs to use deno-ls (lowest priority language server)
  *
```
((nil . ((lsp-disabled-clients . (jsts-ls ts-ls flow-ls)))))
```
  - as a .dir-locals.el file in the directory of my advent of code solutions.
- Javascript now has Iterators & Generators!
- There are also Map objects
  - Arrays used as keys inside a map are not treated by equality, but instead by the array object reference.
- and a strange Symbol class
- Sorting on numbers needs an explicit lambda passed in, otherwise it does it in lexical ordering =/
- Reverse is destructive and modifies the original array while returning the reversed value
- `for…in` shouldn't be used on arrays; it will cast all keys to strings a
- Triggering a profile with deno: deno run –v8-flags=–prof js/day12.js
  - using nodejs to make it readable: node --prof-process isolate-0x5592d54298d0-11331-v8.log
  - Can also use --preprocess to generate a json blob, which can be passed to https://v8.github.io/tools/head/profview/
- Object.values to get values from an object as an array
- Immutable looks interesting, reference from bluepichu's solution
- Pre-allocate a Uint8Array for use
- BigInt is a large integer class, cannot use Math functions with it
  - Suffix numbers with an n to mark them as Bigints
- number.toString(<base>) is super helpful in printing out binary values
- Can use Math.min(...[array]) instead of Math.min.apply(null, array)
- new Array(x) creates an empty array with x length; which means Array.prototype.map becomes a no-op
- Array.prototype.fill is used to fill with a static value: which means filling with a complex object will simply repeat the same object multiple times.
  - I keep making this mistake and should be more careful.
- Deno.inspect() is what generates console.log strings; Deno.inspect(<val>, {depth: <depth>}) allows manually specifying how far to expand the logged values.
Notes on Forth
- Reading from stdin and running forth as a script seems… hard.
Other peoples' code:
- Deno typescript: https://github.com/N8Brooks/aoc_ts/tree/main/year2021
- Bluepichu: https://gist.github.com/bluepichu
Other references
- Getting Programming With Javascript Next was very helpful in picking up new JS concepts.
- MDN is as excellent as always.